package com.qying.suanfa;

public class KMPTest {


    public static void main(String[] args) {

        String aa = "dsadawewq dassdw wewq dsa qwee saa dss asd";

        String bb =  "ababc";
        //String bb =  "dassdw";
        char[] charsBB = bb.toCharArray();
        int[] next = new int[charsBB.length];
        next[0] = -1;
        next[1] = 0;
        int k ;
        //String bb =  "ababc";
        for (int j = 2; j< charsBB.length; j++){
            k = next[j-1];
            while (k != -1) {
                if (charsBB[j-1] == charsBB[k] ){
                    next[j] = k+1;
                    break;
                }else {
                    k = next[k];
                }
                next[j] = 0;
            }
        }

        char[] charsAA = aa.toCharArray();

        int i = 0, j =0;

        while (i < charsAA.length && j< charsBB.length) {
            if (j == -1|| charsAA[i] == charsBB[j]){
                i++;
                j++;
            } else {
                j = next[j];
            }

        }

        if (j == charsBB.length) {
            System.out.println(true);
        }else {
            System.out.println(false);
        }




       /* char[] charAA = aa.toCharArray();
        char[] charBB = bb.toCharArray();

        int i = 0,j=0;

        while (i < charAA.length && j < charBB.length) {
            if (charAA[i] == charBB[j]) {
                i++;
                j++;
            } else {
                i=i-j+1;
                j=0;
            }
        }

        if (j == charBB.length) {
            System.out.println(true);
        }else {
            System.out.println(false);
        }*/


    }

}
